package com.chengzhi.structure;


import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;

/**
 * @description: bst
 * @author: ruanchengzhi
 * @create: 2019-11-30 16:36
 **/
public class BST<E extends Comparable<E>> {
    private Node<E> root;
    private int size;

    public BST() {
        this.root = null;
        this.size = 0;
    }

    public BST(Node<E> root, int size) {
        this.root = root;
        this.size = size;
    }

    public Node<E> getRoot() {
        return root;
    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return Objects.isNull(root);
    }

    /**
     * 插入数据
     *
     * @param e
     * @return: void
     * @author: ruanchengzhi
     * @date: 2020/3/5
     */
    public void add(E e) {
        root = add(root, e);
    }

    private Node add(Node<E> root, E e) {
        if (Objects.isNull(root)) {
            size++;
            return new Node(e);
        }
        if (root.node.compareTo(e) > 0) {
            root.left = add(root.left, e);
        }
        if (root.node.compareTo(e) < 0) {
            root.right = add(root.right, e);
        }
        return root;
    }

    /**
     * 判断是否存在
     *
     * @param e
     * @return: boolean
     * @author: ruanchengzhi
     * @date: 2020/3/5
     */
    public boolean contains(E e) {
        if (Objects.isNull(root)) {
            return false;
        }
        return contains(root, e);
    }

    private boolean contains(Node<E> root, E e) {
        if (root.node.equals(e)) {
            return true;
        } else if (root.node.compareTo(e) < 0) {
            return contains(root.left, e);
        } else if (root.node.compareTo(e) > 0) {
            return contains(root.right, e);
        }
        return false;
    }

    /**
     * 深度优先-前序遍历(先打印参数 中序遍历（中间打印） 后序遍历（最后打印）)
     *
     * @param
     * @return: void
     * @author: ruanchengzhi
     * @date: 2020/3/5
     */
    public void preOrder() {
        preOrder(root);
    }

    private void preOrder(Node<E> root) {
        if (Objects.isNull(root)) {
            return;
        }
        System.out.println(root.node);
        preOrder(root.left);
        preOrder(root.right);
    }

    /**
     * 广度优先遍历层次遍历（利用队列queue）
     *
     * @param
     * @return: void
     * @author: ruanchengzhi
     * @date: 2020/3/5
     */
    public void breadthOrder() {
        Queue<Node<E>> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node Node = queue.remove();
            System.out.println(Node.node);
            if (Objects.nonNull(root.left)) {
                queue.add(root.left);
            }
            if (Objects.nonNull(root.right)) {
                queue.add(root.right);
            }
        }
    }

    /**
     * 删除最小节点
     *
     * @param
     * @return: E
     * @author: ruanchengzhi
     * @date: 2020/3/5
     */
    public E deleteMinNode() {
        if (size == 0) {
            throw new IllegalArgumentException("bst is empty");
        }
        Node<E> minNode = getMinNode(root);
        root = deleteMinNode(root);
        return minNode.node;
    }

    private Node<E> deleteMinNode(Node<E> root) {
        if (root.left == null) {
            Node<E> rightNode = root.right;
            root.right = null;
            size--;
            return rightNode;
        }
        root.left = deleteMinNode(root.left);
        return root;
    }


    private Node<E> getMinNode(Node<E> Node) {
        if (Node.left == null) {
            return Node;
        }
        return getMinNode(Node.left);
    }

    /**
     * 删除最大节点
     *
     * @param
     * @return: E
     * @author: ruanchengzhi
     * @date: 2020/3/5
     */
    public E deleteMaxNode() {
        if (size == 0) {
            throw new IllegalArgumentException("bst is empty");
        }
        Node<E> maxNode = getMaxNode(root);
        root = deleteMaxNode(root);
        return maxNode.node;
    }

    private Node<E> deleteMaxNode(Node<E> root) {
        if (root.right == null) {
            Node<E> leftNode = root.left;
            root.left = null;
            size--;
            return leftNode;
        }
        root.right = deleteMaxNode(root.right);
        return root;
    }

    private Node<E> getMaxNode(Node<E> Node) {
        if (Node.right == null) {
            return Node;
        }
        return getMaxNode(Node.right);
    }

    /**
     * 删除节点
     *
     * @param e
     * @return: void
     * @author: ruanchengzhi
     * @date: 2020/3/6
     */
    public void deleteNode(E e) {
        root = deleteNode(root, e);
    }

    private Node<E> deleteNode(Node<E> node, E e) {
        if (Objects.isNull(node)) {
            return null;
        }
        if (node.node.compareTo(e) < 0) {
            node.left = deleteNode(node.left, e);
            return node;
        } else if (node.node.compareTo(e) > 0) {
            node.right = deleteNode(node.right, e);
            return node;
        } else {
            if (Objects.isNull(node.left)) {
                Node<E> rightNode = root.right;
                root.right = null;
                size--;
                return rightNode;
            }
            if (Objects.isNull(node.right)) {
                Node<E> leftNode = root.left;
                root.left = null;
                size--;
                return leftNode;
            }
            Node<E> minNode = getMinNode(node.right);
            minNode.right = deleteMinNode(node.right);
            minNode.left = node.left;
            node.left = node.right = null;
            return minNode;
        }
    }
}
